package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LongestDivisibleSubset {

	public static void main(String[] args) {
		LongestDivisibleSubset ss = new LongestDivisibleSubset();
		int[] nums = {3, 6, 9, 12, 24, 96, 192, 333, 576, 999};
		ss.largestDivisibleSubset(nums);
	}
	public List<Integer> largestDivisibleSubset(int[] nums) {
		List<Integer> list = new ArrayList<Integer>();
		if (nums == null || nums.length <= 0) {
			return list;
		}
		int[] dp = new int[nums.length];
		Arrays.sort(nums);
		dp[0] = 1;
		for (int i = 1; i < nums.length; i++) {
			for (int j = 0; j < i; j++) {
				// because we are sorted the array, so we can use nums[i] %
				// nums[j]
				// if( (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0) &&
				// dp[j] + 1 > max){
				// let's get the max length first
				if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
					dp[i] = dp[j] + 1;
				}
			}
		}
		for (int i : dp) {
			System.out.print(" " + i);
		}
		System.out.println();
		// and then we should get the max element index
		int maxIndex = 0;
		for (int i = 1; i < nums.length; i++) {
			if (dp[maxIndex] < dp[i]) {
				maxIndex = i;
			}
		}
		int maxNumber = nums[maxIndex];
		int curLength = dp[maxIndex];
		// 注意，加入的时候要注意不是所有可以被maxNumber整除的数都可以加入的
		// 一个很好的办法就是递减地加入
		for (int i = maxIndex; i >= 0; i--) {
			if (maxNumber % nums[i] == 0 && dp[i] == curLength) {
				list.add(0, nums[i]);
				maxNumber = nums[i];
				curLength--; // 也是为了验证是属于最长子集中的元素
			}
		}
		return list;
	}
}
